/*
 * @lc app=leetcode.cn id=300 lang=typescript
 *
 * [300] 最长递增子序列
 */

// @lc code=start
function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const stack = [nums[0]];

  const biranySearch = (arr: number[], target: number) => {
    let l = 0;
    let r = arr.length;
    let mid: number;
    while (l < r) {
      mid = l + ((r - l) >> 1);
      if (arr[mid] >= target) r = mid;
      else l = mid + 1;
    }
    return l;
  };

  for (let i = 1; i < n; i++) {
    const num = nums[i];
    if (num > stack[stack.length - 1]) {
      stack.push(num);
    } else {
      const index = biranySearch(stack, num);
      stack[index] = num;
    }
  }
  return stack.length;
}
// @lc code=end
